package xhhx.test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

//      红黑树性质
//1 红黑树的结点都是红色或者黑色
//2 根结点是黑色
//3 所有叶子都是黑色（这里的叶子结点是空结点）
//4 每个红色结点必须有两个黑色的子结点
//5 从任何一个节点到其每个叶子的所有简单路径都包含相同数目的黑色结点
public class RBTree {
    private int size = 0;
    private Node root = null;

    public int GetSize() {
        return size;
    }

    public void Put(int key) {
        Result result = search(key, root);
        if (result.isFind) {
            return;
        }

        size++;
        if (result.LastNode == null) {
            root = new Node(key, null, null, null, NodeType.Black);
            result.LastNode = root;
            return;
        }

        Node newNode = new Node(key, result.LastNode, null, null);
        if (key < result.LastNode.Key) {
            result.LastNode.Left = newNode;
        } else {
            result.LastNode.Right = newNode;
        }

        adjustAfterInsert(newNode);
    }

    public boolean ContainsKey(int key) {
        Result result = search(key, root);
        return result.isFind;
    }

    public void Remove(int key) {
        Result result = search(key, root);
        if (!result.isFind) {
            return;
        }

        size--;
        Node deleteNode = result.LastNode;

        if (deleteNode.Left != null && deleteNode.Right != null) {
            Node succeedNode = succeed(deleteNode);
            deleteNode.Key = succeedNode.Key;
            deleteNode = succeedNode;
        }

        Node replacement = (deleteNode.Left != null ? deleteNode.Left : deleteNode.Right);
        if (replacement != null) {
            replacement.Parent = deleteNode.Parent;
            if (deleteNode.Parent == null) {
                root = replacement;
            } else if (isLeft(deleteNode)) {
                deleteNode.Parent.Left = replacement;
            } else {
                deleteNode.Parent.Right = replacement;
            }
            deleteNode.Left = deleteNode.Right = deleteNode.Parent = null;

            if (deleteNode.IsBlack()) {
                adjustAfterDelete(replacement);
            }
        } else if (deleteNode.Parent == null) {
            root = null;
        } else {
            if (deleteNode.IsBlack()) {
                adjustAfterDelete(deleteNode);
            }

            if (deleteNode.Parent != null) {
                if (isLeft(deleteNode)) {
                    deleteNode.Parent.Left = null;
                } else {
                    deleteNode.Parent.Right = null;
                }
                deleteNode.Parent = null;
            }
        }

    }

    public void PrintTree() {
        if (root == null) {
            System.out.println("Empty");
        }
        System.out.println("Tree:");
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        int curDepth = 1;
        int col = 0;
        int curSpace = (int) Math.pow((double) 2, (double) (getDepth(root) - 1));

        Map<Node, Integer> mapPos = new HashMap<>();
        mapPos.put(root, curSpace);
        while (queue.peek() != null) {
            Node node = queue.remove();
            int depth = GetNodeDepth(node);
            if (depth > curDepth) {
                curDepth = depth;
                col = 0;
                System.out.print("\n");
                curSpace /= 2;
            }

            int pos = mapPos.get(node);
            for (int i = col; i < pos; i++) {
                System.out.print(" ");
                col++;
            }

            if (node.Type == NodeType.Red) {
                System.out.print("\033[31;4m" + node.Key + "\033[0m");
            } else {
                System.out.print(node.Key);
            }

            if (node.Left != null) {
                queue.add(node.Left);
                mapPos.put(node.Left, pos - curSpace / 2);
            }

            if (node.Right != null) {
                queue.add(node.Right);
                mapPos.put(node.Right, pos + curSpace / 2);
            }

        }

        System.out.println();
    }

    public void Print() {
        if (root == null) {
            System.out.print("Empty");
            return;
        }
        PrintTree();
        System.out.println("Array:");
        LDR(root);

        Remove(3);
        PrintTree();
    }

    private Node succeed(Node node) {
        if (node == null) {
            return null;
        }

        if (node.Right != null) {
            Node curNode = node.Right;
            while (curNode.Left != null) {
                curNode = curNode.Left;
            }
            return curNode;
        } else {
            Node curNode = node.Parent;
            Node child = node;
            if (curNode != null && curNode.Right == node) {
                child = curNode;
                curNode = curNode.Parent;
            }
            return curNode;
        }
    }

    private int succeed(int key) {
        Result result = search(key, root);
        if (!result.isFind) {
            return -1;
        }

        Node succeedNode = succeed(result.LastNode);
        if (succeedNode == null) {
            return -1;
        }
        return succeedNode.Key;
    }

    private void adjustAfterDelete(Node node) {
        while (node != root && node.IsBlack()) {
            Node brother = getBrother(node);
            if (isLeft(node)) {
                if (brother != null && !brother.IsBlack()) {
                    //情况1：待删除节点D的兄弟节点S为红色 调整做法是将父亲节点和兄弟节点的颜色互换，也就是p变成红色，S变成黑色，然后将P树进行AVL树种的RR型操作
                    node.Parent.SetRed();
                    brother.SetBlack();
                    rotataLeft(brother.Parent);
                    brother = node.Parent.Right;
                }

                if ((brother.Left == null || brother.Left.IsBlack()) && (brother.Right == null || brother.Right.IsBlack())) {
                    brother.SetRed();
                    node = node.Parent;
                } else {
                    if (brother.Right == null || brother.Right.IsBlack()) {
                        if (brother.Left != null) {
                            brother.Left.SetBlack();
                        }
                        brother.SetRed();
                        rotataRight(brother);
                        brother = node.Parent.Right;
                    }
                    brother.Type = node.Parent.Type;
                    node.Parent.SetBlack();
                    brother.Right.SetBlack();
                    rotataLeft(node.Parent);
                    node = root;
                }


            } else {
                if (brother != null && !brother.IsBlack()) {
                    node.Parent.SetRed();
                    brother.SetBlack();
                    rotataRight(brother.Parent);
                    brother = node.Parent.Left;
                }
                if ((brother.Right == null || brother.Right.IsBlack()) && (brother.Left == null || brother.Left.IsBlack())) {
                    brother.SetRed();
                    node = node.Parent;
                } else {
                    if (brother.Left == null || brother.Left.IsBlack()) {
                        if (brother.Right != null) {
                            brother.Right.SetBlack();
                        }
                        brother.SetRed();
                        rotataLeft(brother);
                        brother = node.Parent.Left;
                    }
                    brother.Type = node.Parent.Type;
                    node.Parent.SetBlack();
                    brother.Left.SetBlack();
                    rotataRight(node.Parent);
                    node = root;
                }


            }

        }
        node.SetBlack();
    }

    private Result search(int key, Node node) {
        Result result = new Result();
        if (node == null) {
            return result;
        }

        Node curNode = node;
        while (curNode != null) {
            result.LastNode = curNode;
            if (key == curNode.Key) {
                result.isFind = true;
                return result;
            }

            if (key > curNode.Key) {
                curNode = curNode.Right;
            } else {
                curNode = curNode.Left;
            }
        }

        return result;
    }

    private void rotataLeft(Node node) {
        if (node == null) {
            return;
        }

        Node top = node.Parent;
        Node rightNode = node.Right;

        if (node.Parent == null) {
            root = rightNode;
        } else {
            if (node.Parent.Left == node) {
                node.Parent.Left = rightNode;
            } else {
                node.Parent.Right = rightNode;
            }
        }


        node.Parent = rightNode;
        rightNode.Parent = top;

        if (rightNode.Left != null) {
            node.Right = rightNode.Left;
            node.Right.Parent = node;
        } else {
            node.Right = null;
        }
        rightNode.Left = node;

    }

    private void rotataRight(Node node) {
        if (node == null) {
            return;
        }

        Node top = node.Parent;
        Node leftNode = node.Left;

        if (node.Parent == null) {
            root = leftNode;
        } else {
            if (node.Parent.Left == node) {
                node.Parent.Left = leftNode;
            } else {
                node.Parent.Right = leftNode;
            }
        }


        node.Parent = leftNode;
        leftNode.Parent = top;

        if (leftNode.Right != null) {
            node.Left = leftNode.Right;
            node.Left.Parent = node;
        } else {
            node.Left = null;
        }
        leftNode.Right = node;

    }

    private boolean isLeft(Node node) {
        if (node.Parent == null) {
            return false;
        }

        return node == node.Parent.Left;
    }

    private boolean isRight(Node node) {
        if (node.Parent == null) {
            return false;
        }

        return node == node.Parent.Right;
    }

    private Node getBrother(Node node) {
        if (node.Parent == null) {
            return null;
        }

        if (isLeft(node)) {
            return node.Parent.Right;
        } else {
            return node.Parent.Left;
        }
    }

    private void adjustAfterInsert(Node node) {
        if (node.Parent.IsBlack()) {
            // 父亲是黑色节点，不需要调整
            return;
        }

        Node curNode = node;
        while (curNode != null && curNode != root && !curNode.Parent.IsBlack()) {
            if (isLeft(curNode.Parent)) {
                Node uncle = getBrother(curNode.Parent);
                //情况1 父亲和叔叔都是红色节点
                if (!curNode.Parent.IsBlack() && uncle != null && !uncle.IsBlack()) {
                    //父亲结点和叔父结点均为红色，显然无法满足性质4，则将父亲结点和叔父结点绘制成黑色，祖父结点设置成红色
                    curNode.Parent.SetBlack();
                    uncle.SetBlack();
                    uncle.Parent.SetRed();
                    curNode = uncle.Parent;
                } else {
                    if (!isLeft(curNode)) {
                        rotataLeft(curNode.Parent);
                        curNode = curNode.Left;
                    }
                    curNode.Parent.SetBlack();
                    curNode.Parent.Parent.SetRed();
                    rotataRight(curNode.Parent.Parent);
                }
            } else {
                // 对称
                Node uncle = getBrother(curNode.Parent);
                if (!curNode.Parent.IsBlack() && uncle != null && !uncle.IsBlack()) {
                    curNode.Parent.SetBlack();
                    uncle.SetBlack();
                    uncle.Parent.SetRed();
                    curNode = uncle.Parent;
                } else {
                    if (isLeft(curNode)) {
                        rotataRight(curNode.Parent);
                        curNode = curNode.Left;
                    }
                    curNode.Parent.SetBlack();
                    curNode.Parent.Parent.SetRed();
                    rotataLeft(curNode.Parent.Parent);
                }
            }
        }
        root.SetBlack();
    }

    private int GetNodeDepth(Node node) {
        if (node.Parent == null) {
            return 1;
        }
        int depth = 1;
        while (node.Parent != null) {
            depth++;
            node = node.Parent;
        }
        return depth;
    }

    private void LDR(Node node) {
        if (node == null) {
            return;
        }
        LDR(node.Left);
        System.out.print(node.Key + " ");
        LDR(node.Right);
    }

    private int getDepth(Node node) {
        if (node == null) {
            return 1;
        }
        int leftDepth = getDepth(node.Left) + 1;
        int rightDepth = getDepth(node.Right) + 1;
        return leftDepth > rightDepth ? leftDepth : rightDepth;
    }

    private enum NodeType {
        Red,
        Black,
    }

    private static class Node {
        public int Key;
        public Node Parent;
        public Node Left;
        public Node Right;
        public NodeType Type;

        public Node(int key, Node parent, Node left, Node right) {
            this.Key = key;
            this.Parent = parent;
            this.Left = left;
            this.Right = right;
            this.Type = NodeType.Red;
        }

        public Node(int key, Node parent, Node left, Node right, NodeType type) {
            this.Key = key;
            this.Parent = parent;
            this.Left = left;
            this.Right = right;
            this.Type = type;
        }

        public boolean IsBlack() {
            return Type == NodeType.Black;
        }

        public void SetBlack() {
            Type = NodeType.Black;
        }

        public void SetRed() {
            Type = NodeType.Red;
        }
    }

    private static class Result {
        public Node LastNode;
        public boolean isFind;
    }

}
